#pragma once
#ifndef DIV_MUL_H
#define DIV_MUL_H

using ll = long long;
/* 
    gcd 最大公约数
    lcm 最小公倍数
    :: lcm[a,b]>=max(a,b)>=min(a,b)>=gcd(a,b)
    :: gcd(x*a,x*b)=x*gcd(a,b)

    欧几里得算法：辗转相除法
        若 a%b==0,gcd(a,b)=b
        gcd(a,b)=gcd(b,a%b)  (a>b)
    a 3, b 2
    a 2, b 3 % 2 = 1
    a 1, b 2 % 1 = 0
    ret a = 1

    lcm[a,b]*gcd(a,b)==a*b
    lcm[a,b]=a*b/gcd(a,b)
*/

// 最大公约数
int gcd (int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 最小公倍数
int lcm (int a, int b)
{
    return a * b / gcd (a, b);
}

// 计算 n * (2 ^ m)
int mul_PowerOfTwo(int n, int m)
{
    return n << m;
}

// 计算 n / (2 ^ m)
int div_PowerOfTwo(int n, int m)
{
    return n >> m;
}

// 快速幂（暴力）[可能会超ll，复杂度O(n)]
ll ret_power(int a, int b)
{
    ll ret = 1;
    for (int i = 1; i <= b; i++) ret *= a;
    return ret;
}

// 快速幂（优化longlong）
// 同余定理：(a*b) mod p =[(a mod p)*(b mod p)] mod p
ll ret_ll_power(int a, int b, int p)
{
    ll ret = 1;
    for (int i = 1; i <= b; i++)
    {
        ret *= a % p;
        ret %= p;
    }
    return ret;
}

// 快速幂优化（O(logn)）
// 思想升低降次::a^b = pow(a^2, b / 2) * ( b&1 ? a : 1);
ll ret_logn_power(ll a, ll b, ll p)
{
    ll ret = 1;
    while (b)
    {
        b & 1 ? ret = (ret * a) % p : ret;
        a = a * a % p;
        b >>= 1;
    }
    return ret;
}


#endif